package leetcode_1101_1200;

public class LeeCode_1186 {
    public static void main(String[] args) {
//        System.out.println(maximumSum(new int[]{1, -2, 0, 3}));
//        System.out.println(maximumSum(new int[]{1, -2, -2, 3}));
//        System.out.println(maximumSum(new int[]{0,-5,-6,5,0,-5}));
        System.out.println(maximumSum(new int[]{8,-1,6,-7,-4,5,-4,7,-6}));
    }
    private static int maximumSum(int[] arr) {
        int n = arr.length, ans = arr[0];
        int[][] dp = new int[n][2];
        dp[0][0] = arr[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][0] + arr[i], arr[i]);
            dp[i][1] = Math.max(dp[i - 1][1] + arr[i], dp[i - 1][0]);
            ans = Math.max(ans, Math.max(dp[i][0], dp[i][1]));
        }
        return ans;
    }
}
